#include <iostream>
#include <vector>
using namespace std;

class Solution
{
 public:
  // 198.打家劫舍问题
  int rob(vector<int>& nums)
  {
    if (nums.empty())
    {
      return 0;
    }
    int size = nums.size();
    if (size == 1)
    {
      return nums[0];
    }
    // dp[i]的含义：i的范围为0～size-1
    // 因此对于nums[i]偷还是不偷
    vector<int> dp = vector<int>(size, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < size; i++)
    {
      // max(对于nums[i]偷，对于nums[i]不偷)
      dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[size - 1];
  }

  // 213.打家劫舍2
  int rob2
};

int main()
{
  Solution solute;
  vector<int> nums = {1, 2, 3, 1};
  solute.rob(nums);
  return 0;
}